package utility.pathfinding;

import java.util.HashSet;
import java.util.LinkedList;

import model.World;
import model.element.Road;

public class DepthFirstSearch {
	
	private HashSet<Road> visited = new HashSet<Road>();
	private LinkedList<Road> next = new LinkedList<Road>();
	private LinkedList<Road> path = new LinkedList<Road>();

	public LinkedList<Road> depthFirst(Road current, Road end, World w){

		path.addFirst(current);
		visited.add(current);
		for(Road r : current.getNearbyRoads()){
			if(!visited.contains(r)){
				next.addLast(r);
			}
		}
		recursive(end);
		return path;
	}
	
	private boolean recursive(Road goal){
		if(next.isEmpty()){
			return false;
		}
		Road current = next.removeFirst();
		path.addLast(current);
		if(current==goal){
			return true;
		}
		for(Road r : current.getNearbyRoads()){
			if(!visited.contains(r)){
				visited.add(r);
				next.addLast(r);
				if(recursive(goal)){
					return true;
				}
			}
		}
		path.removeLast();
		return false;
	}
	
}
